package leetcode_100;


/**
 *@author 周杨
 *ValidateBinarySearchTree_98 判断一棵树是否是二叉搜索树
 *describe:采用递归的思想 判断左子树和右子树是否都是二叉搜索树 注意边界值情况  AC 97%
 *2018年5月19日 下午3:40:51
 */
public class ValidateBinarySearchTree_98 {
	static class TreeNode{
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode(int x) { val = x; }
	}
	boolean minFlag=true;
	boolean maxFlag=true;
	public static void main(String[] args) {
		System.out.println(Integer.MIN_VALUE+"  "+Integer.MAX_VALUE);
		/*[2,1,3]
		[3,2,null,1,-2147483648]
		[-2147483648,null,2147483647]*/

	}
	
	public boolean isValidBST(TreeNode root) {
		if(root.left==null&&root.right==null)
			return true;
        return help(root,Integer.MIN_VALUE,Integer.MAX_VALUE);
    }	
	public boolean help(TreeNode root,int left,int right) {
		if(root==null)
			return true;
		if(root.val==Integer.MIN_VALUE&&minFlag) {//此前并未出现最小整数
			if(root.left!=null||left!=Integer.MIN_VALUE)
				return false;
			else {
				minFlag=false;
				return help(root.right,left,right);
			}
		}
		if(root.val==Integer.MAX_VALUE&&maxFlag) {//此前并未出现最小整数
			if(root.right!=null||right!=Integer.MAX_VALUE)
				return false;
			else {
				maxFlag=false;
				return help(root.left,left,right);
			}
		}
		
		if(root.val>left&&root.val<right) {
			return help(root.left,left,root.val)&&help(root.right,root.val,right);
		}
		else
			return false;
	}

}
